/*
 *https://leetcode.cn/problems/number-of-digit-one/description/
 *233. 数字 1 的个数
 *difficult 吴朝泽 2024.9.18
 *数位DP
 代码思想基本和 lc357 一样，不同之处在于参数的含义，这里的 pre 参数的含义为已统计的 1 的个数，以及递归调用的条件
*/


class Solution {
public:
    int arr[100];
    long long dp[30][30];

    //pos 表示当前的位数，pre 表示已统计的 1 的个数，flag 表示填的数字大小是否受到限制
    long long DFS(int pos, int pre, bool flag)
    {
        if(pos == 0)  return pre;    //这里要注意返回的是 pre 而不是 1，因为到达了最后一位应该返回前面所有位的 1 的数量
        if(!flag && pre >= 0 && dp[pos][pre] != -1)  return dp[pos][pre];
        int max_num = flag ? arr[pos] : 9;
        long long res = 0;

        for(int i = 0; i <= max_num; ++i)
        {
            if(i == 1)  res += DFS(pos-1, pre+1, flag && i == max_num);
            else        res += DFS(pos-1, pre, flag && i == max_num);
        }
        if(!flag)  dp[pos][pre] = res;
        return res;
    }

    long long check(long long x)
    {
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 10;
            x /= 10;
        }
        return DFS(pos, 0, 1);   //第一个参数表示从最高位开始
    }

    int countDigitOne(int n) 
    {
        memset(arr, 0, sizeof(arr));
        memset(dp, -1, sizeof(dp));
        return check(n);
    }
};